#pragma once
#include <iostream>
#include<assert.h>
using namespace std;

namespace lht {
	template <class T>
	struct ListNode
	{
		struct ListNode* _next;
		struct ListNode* _prev;
		T _data;

		ListNode(const T& data=T()) 
			:_next(nullptr)
			, _prev(nullptr)
			, _data(data)
		{}
	};

	template<class T,class Ref>
	struct __list_iterator
	{
		typedef ListNode<T> Node;
		typedef __list_iterator<T, Ref> self;
		Node* _node;
		__list_iterator(Node*x)
			:_node(x)
		{}

			//++it
		self& operator++() {
			_node = _node->_next;
			return *this;
		}
			
			//it++
		self operator++(int) {
			self tmp(* this);
			_node = _node->_next;
			return tmp;
		}


		//--it
		self& operator--() {
			_node = _node->_prev;
			return *this;
		}

		//it--
		self operator--(int) {
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		Ref operator*() {
			return _node->_data;
		}
		bool operator!=(const self& it) {
			return _node != it._node;
		}
		bool operator==(const self& it) {
			return _node == it._node;
		}
	};

	template<class T>
	class list {
		typedef ListNode<T> Node;
	public:
		typedef __list_iterator<T,T&> iterator; 
		typedef __list_iterator<T,const T&> const_iterator;
		list() {
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		list(size_t n, const T& val = T()) {
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			for (size_t i = 0; i < n; ++i) {
				pushback(val);
			}
		}

		template <class Inputiteraor>
		list(Inputiteraor first, Inputiteraor last) {
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			while (first != last) {
				pushback(*first);
				++first;
			}
		}

		list(const list<T>& ls) {
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			list<T> tmp(ls.begin(), ls.end());
			swap(_head, tmp._head);
		}

		list<T>& operator =(const list<T> ls) {
			swap(_head, ls._head);
			return *this;
		}

	/*	list(const list<T>& ls) {
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			for (auto e : ls) {
				pushback(e);
			}
		}*/

	/*	list<T>& operator =(const list<T>& ls) {
			if (this != &ls) {
				clean();
				for (auto e : ls) {
					pushback(e);
				}
			}
			return *this;
		}*/

		iterator begin() {
			return iterator(_head->_next);
		 }

		iterator end() {
			return iterator(_head);
		}

		const_iterator begin()const {
			return const_iterator(_head->_next);
		}

		const_iterator end()const {
			return const_iterator(_head);
		}
		void pushback(const T& x) {
		/*	Node* newnode = new Node(x);
			Node* tail = _head->_prev;
			tail->_next = newnode; 
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;*/
			insert(end(), x);
		}
		void pushfront(const T& x) {
			insert(begin(), x);
		}

		void popback() {
			erase(--end());
		}

		void popfront() {
			erase(begin());
		}

		void clean() {
			iterator it = begin();
			while (it != end()) {
				iterator del = it++;
				delete del._node;
			}
			_head->_next = _head;
			_head->_prev = _head;
		}

		~list() {
			clean();
			delete _head;
			_head = nullptr;
		}

		iterator insert(iterator pos, const T& x) {
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			return iterator(newnode);
		}

		iterator erase(iterator pos) {
			assert(pos != end());
			Node* cur = pos._node;
			cur->_prev = cur->_next;
			cur->_next = cur->_prev;
			delete cur;
			return iterator(cur->_next);
		}

	private:
		Node* _head;
	};
	void listtest1() {
		list<int> ls;
		ls.pushback(1);
		ls.pushback(2);
		ls.pushback(3);
		ls.pushback(4);
		list<int>::iterator it = ls.begin();
		while (it != ls.end()) {
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	void listtest2() {
		list<int> ls;
		ls.pushback(1);
		ls.pushback(2);
		ls.pushback(3);
		ls.pushback(4);
		list<int> ls2(ls);
		list<int>::iterator it = ls2.begin();
		while (it != ls2.end()) {
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	void listtest3() {
		list<int> ls;
		ls.pushback(1);
		ls.pushback(2);
		ls.pushback(3);
		ls.pushback(4);
		ls.clean();
		list<int>::iterator it = ls.begin();
		while (it != ls.end()) {
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

}